package 中等.队列;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。
 * <p>
 * 不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。
 * <p>
 * 请你设计一个算法，实现：
 * <p>
 * 更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
 * 找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
 * 找到当前记录里股票的 最高价格 。
 * 找到当前记录里股票的 最低价格 。
 * 请你实现 StockPrice 类：
 * <p>
 * StockPrice() 初始化对象，当前无股票价格记录。
 * void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
 * int current() 返回股票 最新价格 。
 * int maximum() 返回股票 最高价格 。
 * int minimum() 返回股票 最低价格 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/stock-price-fluctuation
 */
public class 股票价格波动_2034 {

    public static void main(String[] args) {

        StockPrice stockPrice = new StockPrice();
        stockPrice.update(1, 10);
        stockPrice.update(2, 5);
        System.out.println(stockPrice.current());
        System.out.println(stockPrice.maximum());
        stockPrice.update(1, 3);
        System.out.println(stockPrice.maximum());
        stockPrice.update(4, 2);
        System.out.println(stockPrice.minimum());

    }


}

/**
 * 一个map和两个优先队列进行模拟
 */
class StockPrice {

    private Integer maxTime = 0;

    private Integer curPrice;

    private Map<Integer, Integer> map = new HashMap<>();

    private Queue<Integer> maxPriorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);  //价格大的先出队列

    private Queue<Integer> minPriorityQueue = new PriorityQueue<>((o1, o2) -> o1 - o2);  //价格小的先出队列

    public StockPrice() {

    }

    public void update(int timestamp, int price) {
        if (timestamp >= maxTime) {
            maxTime = timestamp;
            curPrice = price;
        }
        if (map.containsKey(timestamp)) {
            Integer prePrice = map.get(timestamp);
            maxPriorityQueue.remove(prePrice);  //每次remove提高了时间复杂度
            minPriorityQueue.remove(prePrice);
        }
        map.put(timestamp, price);
        maxPriorityQueue.offer(price);
        minPriorityQueue.offer(price);
    }

    public int current() {
        return curPrice;
    }

    public int maximum() {
        return maxPriorityQueue.peek();
    }

    public int minimum() {
        return minPriorityQueue.peek();
    }

}

/**
 * 优先队列中保存时间戳，取出价格时和map中价格做对比
 */
class EfficientStockPrice {

    private Integer maxTime = 0;

    private Integer curPrice;

    private Map<Integer, Integer> map = new HashMap<>();

    private Queue<int[]> maxPriorityQueue = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);  //价格大的先出队列

    private Queue<int[]> minPriorityQueue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);  //价格小的先出队列

    public EfficientStockPrice() {

    }

    public void update(int timestamp, int price) {
        if (timestamp >= maxTime) {
            maxTime = timestamp;
            curPrice = price;
        }
        map.put(timestamp, price);
        maxPriorityQueue.offer(new int[]{timestamp, price});
        minPriorityQueue.offer(new int[]{timestamp, price});
    }

    public int current() {
        return curPrice;
    }

    public int maximum() {
        while (true) {
            int[] peek = maxPriorityQueue.peek();  //取出头部元素
            //因为队列中的元素同一个timestamp可能存在多个，如果头部元素和最新的map中timestamp价格不一致，将队列中的元素去除
            if (peek[1] != map.get(peek[0])) {
                maxPriorityQueue.poll();
            } else {
                return peek[1];
            }
        }
    }

    public int minimum() {
        while (true) {
            int[] peek = minPriorityQueue.peek();
            if (peek[1] != map.get(peek[0])) {
                minPriorityQueue.poll();
            } else {
                return peek[1];
            }
        }
    }

}